import time,resource,math,random,os

INF = 10e10

def length(worker:list,task:list)->float:#求两个点的长度
    distance = (worker[2]-task[2])**2+(worker[3]-task[2])**2
    distance = pow(distance,1/2)
    return distance

def length2(worker:list,task:list)->float:#求两个点的长度,不开方的
    distance = (worker[2]-task[2])**2+(worker[3]-task[3])**2
    return distance

def satisfyLoc(worker:list,task:list)->bool:#验证任务与工作者之间是否符合活动范围内
    if length2(worker,task) > worker[4]*worker[4]:
        return False
    return True

def satifyTime(worker:list,task:list)->bool:#检查是否满足时间要求
    if (worker[0] < task[4] and task[0] < worker[6]) is False:
        return False
    return True

def satify(worker:list,task:list)->bool:#检查是否满足
    if satifyTime(worker,task) and satisfyLoc(worker,task):
        return True
    return False
    
def calcCost(worker:list,task:list)->float:
    if satisfyLoc(worker,task) and satifyTime(worker,task):
        return worker[7]*task[5]
    else:
        return 0.0

def dcmp(a:float,b:float)->bool:
    return math.isclose(a,b,rel_tol=1e-6)
def dcmp(a:float)->bool:
    return abs(a)<1e-6


workers = []
tasks = []
queue = []
workerNum = 0
taskNum = 0
utilityMax = 0
def readData(fileName):
    global workerNum
    global taskNum
    global utilityMax
    with open(fileName,'r') as f:
        data = f.readlines()
        first = data[0].strip("\n").split(" ")
        workerNum = int(first[0])
        taskNum = int(first[1])
        utilityMax = int(first[2])
        for i in range(1,len(data)):
            node = data[i].strip("\n").split(" ")
            if node[1]=='w':
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=float(node[4])#半径
                node[5]=int(node[5])#能力
                node[6]=int(node[6])+node[0]#停留的时间
                node[7]=float(node[7])#接受率
                if len(node) < 9:#最后一个用来记录等待多久匹配
                    node.append(0)
                else:
                    node[8] = 0
                workers.append(node)
            else:
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=int(node[4])+node[0]#停留的时间
                node[5]=float(node[5])#支付的报酬
                if len(node) < 7:
                    node.append(0)
                else:
                    node[6] = 0
                tasks.append(node)
            queue.append(node)
    return workerNum,taskNum,utilityMax

Qtable = []
ALPHA = 0.01 #学习率
GAMMA = 0.98 #折扣因子
EPSILON = 0.01#探索的概率



def initQ(action):
    Qtable.clear()
    for i in range(workerNum):
        Qtable.append([])
        for j in range(taskNum):
            Qtable[i].append([])
            for k in range(action):
                initData = 0.000001*random.randint(0,100)
                Qtable[i][j].append(initData)
    # print(len(Qtable[0][0]))
    
def maxAction(aList:list):
    maxValue = -1
    position = 0
    for index,value in enumerate(aList):
        if value >= maxValue:
            position = index
            maxValue = value
    return position
def selectTask(arrWorkers:list,mWorkers:list,mTasks:list,curA,curTime):
    uCost = 0
    maxCost = 0
    tempCost = 0
    mtindex = -1
    matchNum = 0
    wsize = len(arrWorkers)
    threshold = math.exp(curA)
    removeWorkers = [False for i in range(wsize)]
    for w in range(wsize):#逐个工作者匹配
        maxCost = 0
        mtindex = -1
        deadlineI = -1#删除超时
        for t in range(len(mTasks)):
            tempCost = calcCost(arrWorkers[w],mTasks[t])
            if tempCost >= threshold and tempCost > maxCost and arrWorkers[w][6] >= curTime and mTasks[t][4] >= curTime:
                maxCost = tempCost
                mtindex = t
            if mTasks[t][4] < curTime:
                deadlineI = t
        if mtindex != -1:#说明匹配成功
            uCost += maxCost
            mTasks.pop(mtindex)
            matchNum += 1
            removeWorkers[w] = True
        if deadlineI != -1:
            mTasks.pop(deadlineI)
    for w in range(wsize):
        if removeWorkers[w] == False:
            mWorkers.append(arrWorkers[w])
    return uCost,matchNum
            
def selectWorker(arrTasks:list,mTasks:list,mWorkers:list,curA,curTime):
    uCost = 0
    maxCost = 0
    tempCost = 0
    mwindex = -1
    matchNum = 0
    tsize = len(arrTasks)
    threshold = math.exp(curA)
    removeTasks = [False for i in range(tsize)]
    for t in range(tsize):
        maxCost = 0
        mwindex = -1
        deadlineI = -1#删除超时
        for w in range(len(mWorkers)):
            tempCost = calcCost(mWorkers[w],arrTasks[t])
            if tempCost >= threshold and tempCost > maxCost and arrTasks[t][4] >= curTime and mWorkers[w][6] >= curTime:
                maxCost = tempCost
                mwindex = w
            if mWorkers[w][6] < curTime:
                deadlineI = -1
        if mwindex != -1:
            uCost += maxCost
            mWorkers.pop(w)
            matchNum += 1
            removeTasks[t] = True
        if deadlineI != -1:
            mWorkers.pop(deadlineI)
    for t in range(tsize):
        if removeTasks[t] == False:
            mTasks.append(arrTasks[t])
    return uCost,matchNum

def removeDeadline(mWorkers:list,mTasks:list,curTime):
    retainWorkers = [True for i in range(len(mWorkers))]
    retainTasks = [True for i in range(len(mTasks))]
    for index,w in enumerate(mWorkers):
        if w[6] < curTime:
            retainWorkers[index] = False
    for index,t in enumerate(mTasks):
        if t[4] < curTime:
            retainTasks[index] = False
    
    wans = []
    tans = []

    for index,flag in enumerate(retainWorkers):
        if flag == True:
            wans.append(mWorkers[index])
    for index,flag in enumerate(retainTasks):
        if flag ==True:
            tans.append(mTasks[index]) 
    return wans,tans

def VBTA():
    theta = round(math.log(utilityMax+1.0),0)
    theta = int(theta)
    action = theta
    initQ(action)
    mworkers = []
    mtasks = []
    curTime = 0
    utility = 0.0
    curA = 0
    lastA = 0
    #当前状态
    lastWnu = 0
    lastTnu = 0
    #下一个状态
    wnu = 0
    tnu = 0
    reward = 0
    matchNum = 0
    
    for item in queue:
        arrWorkers = []
        arrTasks = []
        curTime = item[0]
        crowType = item[1]
        if crowType == "w":
            cap = item[5]
            for w in range(cap):#把能力转化为多个同样的工作者
                arrWorkers.append(item)
        else:
            arrTasks.append(item)
        #选择动作
        probability = random.random()
        if probability < EPSILON:
            curA = random.randint(0,action-1)#随机选所有动作的一个
        else:
            curA = maxAction(Qtable[lastWnu][lastTnu])#选择当前状态
        if crowType =="w":
            reward,tempN = selectTask(arrWorkers,mworkers,mtasks,curA,curTime)
        else:
            reward,tempN = selectWorker(arrTasks,mtasks,mworkers,curA,curTime)
        utility += reward
        matchNum += tempN
        wnu = len(mworkers)%workerNum #求余为了保证工作者数量不超出Q表范围
        tnu = len(mtasks)%taskNum
        #更新Q表
        # print(workerNum,taskNum,len(Qtable[wnu][tnu]),wnu,tnu,lastA)
        Qtable[lastWnu][lastTnu][lastA] += ALPHA*(reward+GAMMA*max(Qtable[wnu][tnu])-Qtable[lastWnu][lastTnu][lastA])
        lastA = curA
        lastWnu = wnu
        lastTnu = tnu
        mworkers,mtasks = removeDeadline(mworkers,mtasks,curTime)
    return utility,matchNum

def solve():
    memory = resource.getrusage(resource.RUSAGE_SELF)
    avgUtility = 0.0
    avgTime = 0
    avgMemory = 0
    avgMatchNu = 0
    startTime = time.perf_counter()
    avgUtility,avgMatchNu = VBTA()
    endTime = time.perf_counter()
    avgTime = endTime - startTime
    avgMemory = memory.ru_maxrss
    # print(avgUtility,avgTime,avgMemory,avgMatchNu)
    return [avgUtility,avgTime,avgMemory,avgMatchNu]


def varyWorkers(testNUm):#测试变化的工作者，其余变量保持不变
    fin = open("./result/synthetic/data/varyworkers.txt",'a+',encoding='utf-8')
    for w in  [100, 200, 500, 1000, 5000]:
        fileName = f"./dataset/synthetic/{w}_2500_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyTasks(testNUm):#测试变化的工作者
    fin = open("./result/synthetic/data/varytasks.txt",'a+',encoding='utf-8')
    for t in   [500, 1000, 2500, 5000, 10000]:
        fileName = f"./dataset/synthetic/500_{t}_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyCw(testNUm):#测试工作者能力变化的影响
    fin = open("./result/synthetic/data/varycw.txt",'a+',encoding='utf-8')
    for cw in [1, 2, 3, 4, 5]:
        fileName = f"./dataset/synthetic/500_2500_{cw}_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyRw(testNUm):#测试工作者半径变化的影响
    fin = open("./result/synthetic/data/varyrw.txt",'a+',encoding='utf-8')
    for rw in [1.0, 1.5, 2.0, 2.5, 3.0]:
        fileName = f"./dataset/synthetic/500_2500_1_{rw}_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyDw(testNUm):#工作者接受率变化的影响
    fin = open("./result/synthetic/data/varydw.txt",'a+',encoding='utf-8')
    for dw in [0.1, 0.3, 0.5, 0.7, 0.9]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_{dw}_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyDdl(testNUm):#截至时间变化的影响
    fin = open("./result/synthetic/data/varyddl.txt",'a+',encoding='utf-8')
    for ddl in [2, 4, 6, 8, 10]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_{ddl}_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsNormal(testNUm):#正态分布任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsnormal.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsExponentail(testNUm):#指数分布任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsexponentail.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt+100}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsUniform(testNUm):#任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsuniform.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt+1000}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def scalability(testNUm):
    fin = open("./result/synthetic/data/scalability.txt",'a+',encoding='utf-8')
    for s in range(1,11):
        w = s*10**3
        t = s*10**4
        fileName = f"./dataset/synthetic/{w}_{t}_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def EverySenderCw(testNUm):#真实数据集
    fin = open("./result/real/data/varyEverysenderCw.txt",'a+',encoding='utf-8')
    for cap in [1,2,3,4,5,6,7,8,9,10]:
        fileName = f"./dataset/real/EverySender_cap{cap}/data_00_time.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve()
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "VBTA"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def  gMissionCw(testNUm):
        fin = open("./result/real/data/varygMissionCw.txt",'a+',encoding='utf-8')
        for cap in [1,2,3,4,5,6,7,8,9,10]:
            fileName = f"./dataset/real/gMission_cap{cap}/data_00_time.txt"
            ansList = [0,0,0,0]
            if os.path.exists(fileName):
                workers.clear()
                tasks.clear()
                queue.clear()
                readData(fileName)
                for n in range(testNUm):#测试次数
                    ans=solve()
                    for ansi in range(4):
                        ansList[ansi] += ans[ansi]
                writeStr = "VBTA"
                for result in ansList:
                    temp = result/testNUm
                    print(temp,end=' ')
                    writeStr +=" "+str(temp)
                print()
                writeStr += "\n"
                fin.write(writeStr)
            else:
                print(fileName,"文件不存在")

if __name__ =="__main__":
    testNUm = 1
    # varyWorkers(testNUm)
    # varyTasks(testNUm)
    # varyCw(testNUm)
    # varyRw(testNUm)
    # varyDw(testNUm)
    # varyDdl(testNUm)

    # varyPtsNormal(testNUm)
    # varyPtsExponentail(testNUm)
    # varyPtsUniform(testNUm)

    scalability(testNUm)

    # EverySenderCw(testNUm)
    # gMissionCw(testNUm)
    
